今天討論 priority queue 的題目。

以下是 Python-LeetCode 581 第五招 優先佇列 Priority Queue/Heap中介紹 priority queue的文字:

優先佇列(Priority Queue，簡稱PQ)，也常以其實作方式 Heap 來稱呼，是一個教科書很標準、應用很廣的資料結構。相對於先進先出的Queue、先進後出的Stack、雙端開口的Deque，PQ具有優先權概念，優先權高的會先出來。

Priority Queue 的適用場景

多次找最大/最小值，並且資料可能變動的情況。倘若只有一次查找最大/最小值，那就用 sort即可。

(這適用於我 todo list，每個任務都有重要程度的分數，而我最該開始做的任務就得是那一件最火燒屁股的任務:))

1942. The Number of the Smallest Unoccupied Chair (Medium)

題目敘述:
有一個聚會，有n位朋友到，現場有編號從 0 到無限大的椅子，編號從0到n-1的朋友逐一在不同時間點到場，一到場就坐那一個編號最小的椅子。當朋友離開聚會時，他們的椅子在他們離開的那一刻就被收回，如果另一個朋友同時到達，他們可以坐在那張椅子上。

給定一個 0 索引的二維整數數組 times，其中 times[i] = [arrivali, lefti]，分別表示第 i 個朋友的到達和離開時間，以及一個整數 targetFriend。回傳編號為 targetFriend 的好友將坐的椅子編號。

解題想法:
用 min-heap 去管理所有空的椅子。
有人到場就得，最小編號椅子就會被占住，直接對 min heap 做pop，這動作 O(logN)
有人離開，他的椅子編號就會被 push 回 min heap 做管理加編號排序，動作同樣 O(log N)

我用 for 模擬派對所有時間點，椅子去留的變化。
小注意點是，題目只寫一個時間只有一個人入座，因此一個時間可能有多人離開。

class Solution {
public:
    int smallestChair(vector<vector<int>>& times, int targetFriend) {
        int n = times.size();

        // Separate arrival and leave events
        vector<pair<int, int>> arrival(n), leave(n);

        // Array to track which seat each friend sits in
        vector<int>seatAssigned (times.size()); 
        
        for (int i = 0; i < times.size(); i++) {
            arrival[i] = {times[i][0], i}; // {arrival time, friendID}
            leave[i] = {times[i][1], i};   // {leave time, friendID}
        }

        // Sort arrival and leave by time
        sort(arrival.begin(), arrival.end());
        sort(leave.begin(), leave.end());

        // min-heap
        priority_queue<int, vector<int>, greater<int>> availableSeats; 
        // Initialize the availableSeats with numbers
        for (int i = 0; i < times.size(); i++) {
            availableSeats.push(i);
        }

        int arriIdx = 0, leavIdx = 0, lastOneLeave = leave[leave.size()-1].first;
        for (int i = 0; i <= lastOneLeave; i++) {
            while (leave[leavIdx].first == i) {
                // return his seat
                availableSeats.push(seatAssigned[leave[leavIdx].second]); 
                leavIdx++;
            }
            if (arrival[arriIdx].first == i) {
                int minSeat = availableSeats.top();
                int friendId = arrival[arriIdx++].second;
                if (friendId == targetFriend) 
                    return minSeat;
                availableSeats.pop();
                seatAssigned[friendId] = minSeat;
            }
        }
        return seatAssigned[targetFriend];
    }
};

時間複雜度: O(NlogN+M), 排序需 O(NlogN) 加上 push, pop 各操作最多 N 次，因此對 min heap 操作的時間也是 O(NlogN)，然後由於我模擬整個派對時間(M)，因此時間複雜度上加 M。

優化我的程式:
看 吳邦一教授寫這題。
教授沒有像我去模擬所有時間點(很有可能很多時間是沒做事的)，而是在去迭代所有人的抵達時間，在抵達時間i，先將所有在這抵達時間i前就離開的人的椅子全收回來，接著再分配最小的空椅子給這抵達的朋友。